package Hot100.Medium.GreedyAndDP.DynamicPlanning.bag_01;

import java.util.Arrays;

public class LC494_SumOfTarget {
    public static void main(String[] args) {

    }

    /**
     * dp[][]数组法，也就是动态规划，用二维数组模拟01背包，是一个转换01背包问题
     * 假设加法的总和为x，那么减法对应的总和就是sum - x。
     * 所以我们要求的是 x - (sum - x) = target
     *
     * x = (target + sum) / 2
     *
     * 此时问题就转化为，用nums装满容量为x的背包，有几种方法。
     * 这里的x，就是bagSize，也就是我们后面要求的背包容量。
     *
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays1(int[] nums, int target){
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和
        // 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）
        if(sum < Math.abs(target)){
            return 0;
        }

        // 利用二元一次方程组将left用target和sum表示出来，转换为01背包问题，left就变成了包容量，要用nums里面的数往背包里放
        // 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的,因此直接返回
        if((sum + target) % 2 != 0) {
            return 0;
        }
        int left = (sum + target) / 2;
        // dp[i][j]含义遍历到数组第i个数时，left为j时的能装满背包的方法总数
        int[][] dp = new int[nums.length][left + 1];
        // 初始化dp数组
        // 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
        // 其他情况dp[0][j] = 0，java整数数组默认初始值为0
        if (nums[0] <= left) {
            dp[0][nums[0]] = 1;
        }

        // 初始化最左列（dp[i][0])
        // 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
        // n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）
        int numZeros = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);

        }
        // 确定递推公式
        // 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
        // nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]
        // 由递推公式可知，先遍历i或j都可
        for(int i = 1; i < nums.length; i++){
            for(int j = 1; j <= left; j++){
                if(nums[i] > j){
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.length - 1][left];
    }

    public int findTargetSumWays(int[] nums, int target) {
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        // 问题变成从nums选一些数，使得这些数的元素和恰好等于p或q的方案数
        s = s - Math.abs(target);
        if (s < 0 || s % 2 == 1) {
            return 0;
        }

        int m = s / 2; // 背包容量，要数的是 有多少子集 N 的和为 m。
        int n = nums.length;
        int[][] memo = new int[n][m + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }

        return dfs(n - 1, m, nums, memo);
    }

    private int dfs(int i, int c, int[] nums, int[][] memo){
        if(i < 0){
            return c == 0 ? 1 : 0;
        }
        if(memo[i][c] != -1){
            return memo[i][c];
        }
        int res = dfs(i - 1, c, nums, memo);// 不选
        if(c >= nums[i]){
            res = res + dfs(i -1, c - nums[i], nums, memo); // 选当前数，目标和c减去nums[i]
        }
        return memo[i][c] = res;
    }
}
